package Hot100.BackTracking;

import java.util.ArrayList;
import java.util.List;

public class exist {
    public static void main(String[] args) {
        char[][] board = {{'a','b'}};
        String word = "ba";
        System.out.println(new exist().exist(board,word));
    }

    List<String> result = new ArrayList<>();
    String path = "";

    public boolean exist(char[][] board, String word) {
        int[][] used = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if(board[i][j] == word.charAt(0)){
                    path += board[i][j];
                    used[i][j] = 1;
                    backTracking(board,word,i,j,1,used);
                    path = path.substring(0,path.length() - 1);
                    used[i][j] = 0;
                    if(!result.isEmpty()){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    public void backTracking(char[][] board,String word,int row,int col,int length,int[][] used){
        if(length == word.length()){
            if(path.equals(word)){
                result.add(path);
                return;
            }else {
                return;
            }
        }

        if(row - 1 >= 0 && used[row -1][col] == 0 && board[row - 1][col] == word.charAt(length)){
            path += board[row-1][col];
            used[row - 1][col] = 1;
            backTracking(board,word,row - 1,col,length + 1,used);
            path = path.substring(0,path.length() - 1);
            used[row -1][col] = 0;
        }
        if(row + 1 < board.length && used[row + 1][col] == 0 && board[row + 1][col] == word.charAt(length)){
            path += board[row+1][col];
            used[row + 1][col] = 1;
            backTracking(board,word,row + 1,col,length + 1,used);
            path = path.substring(0,path.length() - 1);
            used[row + 1][col] = 0;
        }
        if(col - 1 >= 0 && used[row][col - 1] == 0 && board[row][col - 1] == word.charAt(length)){
            path += board[row][col - 1];
            used[row][col - 1] = 1;
            backTracking(board,word,row,col - 1,length + 1,used );
            path = path.substring(0,path.length() - 1);
            used[row][col - 1] = 0;
        }
        if(col + 1 < board[0].length && used[row][col + 1] == 0 && board[row][col + 1] == word.charAt(length)){
            path += board[row][col + 1];
            used[row][col + 1] = 1;
            backTracking(board,word,row,col + 1,length + 1,used);
            path = path.substring(0,path.length() - 1);
            used[row][col + 1] = 0;
        }
    }

}
